/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function (board, word) {
  let m = board.length
  let n = board[0].length

  function dfs(i, j, k) {
    //边界条件判断
    if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] !== word[k]) return false
    if (k === word.length - 1) return true

    //暂存现场
    let temp = board[i][j]
    //标记访问过
    board[i][j] = '#'

    //向上、下、左、右四个方向继续递归
    const res =
      dfs(i - 1, j, k + 1) ||
      dfs(i + 1, j, k + 1) ||
      dfs(i, j - 1, k + 1) ||
      dfs(i, j + 1, k + 1)

    //恢复现场
    board[i][j] = temp

    //返回结果
    return res
  }

  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      // 一旦找到路径就返回 true
      if (dfs(i, j, 0)) return true
    }
  }
  // 所有格子都试过了都不行才返回 false
  return false
};